package algorithmExample.stack;

import java.util.Stack;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/12 10:53
 */
//题目：https://leetcode-cn.com/problems/trapping-rain-water/
public class TrappingRainWater {
    public int trap(int[] height) {
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            int leftMax = 0, rightMax = 0;
            for (int j = i; j >= 0; j--) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int k = i; k < height.length; k++) {
                rightMax = Math.max(rightMax, height[k]);
            }
            result += Math.max(Math.min(leftMax, rightMax) - height[i], 0);
        }
        return result;
    }

    public int trap2(int[] height) {
        Stack<Integer> stack = new Stack();
        int result = 0;
        for (int current = 0; current < height.length; current++) {

            while (!stack.isEmpty() && height[stack.peek()] < height[current]) {

                Integer pos = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int distance = current - stack.peek() - 1;
                result += Math.max(Math.min(height[stack.peek()], height[current]) - height[pos], 0) * distance;

            }
            stack.add(current);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] input = new int[]{4, 2, 0, 3, 2, 5};
//        int[] input = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        int result = new TrappingRainWater().trap2(input);
        System.out.printf("result is %s", String.valueOf(result));
    }
}
